Advanced Topics in Computer Science (238901)
Spring semester 2010
last updated: 09.03.2010
Graph polynomials and their Complexity
NEW (1.3.2010):
List of topics for seminar talks.
NEW (1.3.2010):
Slides of given lectures
For those graduate students who have already taken 238901 before,
but on another topic, arrangements will be found
to get credit again.
Lecturer: Prof. J.A. Makowsky and participants
NEW TIME: Sunday, 10:30-12:30
New Place: Taub 601
Prerequisites:
Computability, some elementary graph theory,
some familiarity with linear and abstract algebra.
Format:
Two hours frontal presentations.
Requirements:
Edited version of frontal presentation or
final project.
Outline
A common generalization of counting problems are graph polynomials.
The most prominent of these are the matching polynomials,
the colouring polynomials and the Tutte polynomial.
For general graphs these are often hard to compute (#P hard).
There are also various multivariate generalizations
of these polynomials.
-
A catalogue of prominent graph polynomials.
Slides on prominent polynomials from 238900-2006:
http://www.cs.technion.ac.il/~janos/COURSES/238900/slides.html
ISF funded research project on
Graph Polynomials:
http://www.cs.technion.ac.il/~janos/RESEARCH/gp-homepage.html
-
Distinctive power of graph polynomials
-
Reducibilities between graph polynomials
-
Easy and difficult evaluations of graph polynomials
-
Towards an algebraic complexity theory